/*
 * 2.4
 * You have two numbers represented by a linked list, where each node contains a sin-
 * gle digit. The digits are stored in reverse order, such that the 1’s digit is at the head of
 * the list. Write a function that adds the two numbers and returns the sum as a linked
 * list.
 * EXAMPLE
 * Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
 * Output: 8 -> 0 -> 8
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct _node_t {
    int v;
    struct _node_t *next;
} node_t;

node_t *new_node(int v)
{
    node_t *node = (node_t *)malloc(sizeof(node_t));
    node->v = v;
    return node;
}

node_t *add_node(node_t *node1, node_t *node2)
{
    if (!node1 || !node2) {
        return NULL;
    }
    node_t *n1 = node1, *n2 = node2;
    node_t *new_list, *p = NULL, *t;
    int carry = 0;
    while (n1 && n2) {
        int v = (n1->v + n2->v + carry) % 10;
        carry = (n1->v + n2->v + carry) / 10;
        t = new_node(v);
        if (!p) {
            new_list = p = t;
        } else {
            p->next = t;
            p = t;
        }
        n1 = n1->next;
        n2 = n2->next;
    }
    if (carry) {
        t = new_node(carry);
        p->next = t;
    }
    return new_list;
}

int main()
{
    node_t *node1 = new_node(3);
    node1->next = new_node(1);
    node1->next->next = new_node(5);
    node_t *node2 = new_node(5);
    node2->next = new_node(9);
    node2->next->next = new_node(2);
    node_t *node_list = add_node(node1, node2);
    /* print & free */
    node_t *curr, *prev = node_list;
    while (prev) {
        curr = prev->next;
        printf("%d ", prev->v);
        free(prev);
        prev = curr;
    }
    printf("\n");
}
